/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 */

// @lc code=start
class Solution
{
public:
  typedef vector<vector<int>> Matrix;

  int len;
  Matrix ans;

  vector<vector<int>> combine(int n, int k)
  {
    this->len = k;
    vector<int> tmp;
    Backtracking(1, n, tmp);
    return ans;
  }

  void Backtracking(int start, int limit, vector<int>& tmp)
  {
    if (tmp.size() == len)
      ans.push_back(tmp);
    else {
      for (int i = start; i <= limit; ++i) {
        tmp.push_back(i);
        Backtracking(i + 1, limit, tmp);
        tmp.pop_back();
      }
    }
  }
};
// @lc code=end
